package com.dong.arithmetic.tree;

/**
 * 中序遍历：左--->根--->右
 *
 * @author jianyang206881
 * @date 2018/7/23
 */
public class LDR extends CreateTree {
    private TreeNote treeNote;

    public static void main(String[] args) {
        LDR ldr = new LDR();
        TreeNote treeNote = ldr.create(15);

        ldr.traversal(treeNote, null);
        System.out.println("\n");

        ldr.traversal(treeNote, 5);
        System.out.println("\ntraversal: " + ldr.treeNote.getValue());

        TreeNote nextNote = ldr.next(ldr.treeNote);
        System.out.println("\nnext: " + (nextNote == null ? null : nextNote.getValue()) + "\n");

        ldr.treeNote = null;
        ldr.traversalNext(treeNote, 11);
        System.out.println("\ntraversalNext: " + ldr.treeNote.getValue());

    }

    /**
     * 返回下一个节点
     *
     * @param treeNote 当前节点
     * @return 下一个节点
     */
    private TreeNote next(TreeNote treeNote) {

        // 判断右节点
        TreeNote rightNote = treeNote.getRight();
        if (rightNote == null) {
            // 右节点空，该节点或者父父父。。。节点为爷爷节点的左节点时，爷爷节点就是下一个节点
            return this.firstLeftNote(treeNote);
        } else {
            // 右节点非空，如果右节点没有左节点，那么右节点就是下一个节点。如果右节点有左节点，那么左左左。。。节点就是下一个节点
            return this.finallyLeftNote(rightNote);
        }
    }

    private TreeNote finallyLeftNote(TreeNote treeNote) {
        TreeNote leftNote = treeNote.getLeft();

        if (leftNote == null) {
            return treeNote;
        } else {
            return this.finallyLeftNote(leftNote);
        }
    }

    private TreeNote firstLeftNote(TreeNote treeNote) {
        TreeNote parentNote = treeNote.getParent();

        // 根节点，没有右子树
        if (parentNote == null) {
            return null;
        }

        // 如果是父节点的左节点，那么父节点就是下一个节点
        if (treeNote.equals(parentNote.getLeft())) {
            return parentNote;
        }

        // 继续向上判断父节点
        return firstLeftNote(parentNote);
    }

    /**
     * 遍历并返回下一个值的节点
     *
     * @param treeNote 数
     * @param value    节点值
     */
    private void traversalNext(TreeNote treeNote, Integer value) {
        if (treeNote.getLeft() != null) {
            this.traversalNext(treeNote.getLeft(), value);
        }

        System.out.print(treeNote.getValue() + " ");
        if (this.treeNote != null) {
            this.treeNote = treeNote;
            return;
        }
        if (value != null && value.equals(treeNote.getValue())) {
            this.treeNote = treeNote;
        }

        if (treeNote.getRight() != null) {
            this.traversalNext(treeNote.getRight(), value);
        }
    }

    /**
     * 遍历并返回指定节点
     *
     * @param treeNote 数
     * @param value    节点值
     */
    private void traversal(TreeNote treeNote, Integer value) {
        if (value != null && value.equals(treeNote.getValue())) {
            this.treeNote = treeNote;
            return;
        }
        if (this.treeNote != null) {
            return;
        }

        if (treeNote.getLeft() != null) {
            this.traversal(treeNote.getLeft(), value);
        }

        System.out.print(treeNote.getValue() + " ");

        if (treeNote.getRight() != null) {
            this.traversal(treeNote.getRight(), value);
        }
    }
}
